#define _CRT_SECURE_NO_WARNINGS 1
#include <climits>
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid)
    {
        int row = grid.size(), col = grid[0].size();
        vector<int> dp1(col, INT_MAX);
        dp1[0] = 0;
        vector<int> dp2(col, 0);
        for (int i = 0;i < row;++i)
        {
            for (int j = 0;j < col;++j)
            {
                if (j == 0) dp2[j] = grid[i][j] + dp1[j];
                else dp2[j] = grid[i][j] + min(dp1[j], dp2[j - 1]);
            }
            swap(dp1, dp2);
        }
        return dp1.back();
    }
};